$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Тастатура

време меморија улаз излаз
0,7 s 64 Mb стандардни излаз стандардни улаз

На телевизорима се користе тастатуре на екранима које омогућавају да се текст унесе само коришћењем пет тастера на даљинском управљачу – четири стрелице и тастера ОК. Тастатура је подељена у правоугаону мрежу квадратића, при чему се неки “тастери” протежу преко већег броја квадратића. Пример такве тастатуре је приказан на слици.

Пример тастатуре – курсор се налази изнад карактера N

Курсор се увек налази изнад једног квадратића. Када се притисне тастер ОК на текст се дописује карактер који пише на том квадратићу. Када се притисне једна од четири стрелице, не прелази се увек на следећи квадратић, већ се прелази на први квадратић у смеру стрелице на ком није написан исти карактер као и на полазном квадратићу. Ако такав квадратић не постоји, курсор се не помера.

На пример, ако се притисне стрелица на десно док је курсор на квадратићу A у горњем левом углу тастатуре (на позицији \((0, 0)\)), наредни квадратић на коме такође пише A се прескаче и долази се на први квадратић на коме пише B (на позицији \((0, 2)\)). Ако се притисне стрелица на доле, прелази се на квадратић на коме пише G (на позицији \((1, 0)\)). Ако се притисне стрелица на горе или на лево, курсор се не помера.

Карактери на тастатури се не понављају – сваком карактеру одговара највише један “тастер”, али он може бити састављен од више квадратића и не мора бити правоугаоног облика. Тастататура обавезно садржи и тастер Enter који је означен карактером * који је потребно притиснути на крају уноса текста.

Напиши програм који одређује најмањи број притисака тастера потребних да се откуца дати текст.

Улаз

Са стандардног улаза се учитавају димензије правоугаоне мреже \(v \times k\) (\(1 \leq v, k \leq 50\)). Након тога се уноси матрица карактера која описује тастатуру. На крају се уноси линија текста коју је потребно откуцати (она садржи највише \(10~000\) карактера). Сви карактери у тексту сигурно постоје на тастатури.

Излаз

На стандардни излаз исписати најмањи број притисака тастера помоћу којих се може откуцати тражени текст.

Пример 1

Улаз

4 7 ABCDEFG HIJKLMN OPQRSTU VWXYZ** CONTEST

Излаз

30

Пример 2

Улаз

2 4 AABB DCC* BCDA

Излаз

12

Објашњење

Један редослед притискања тастера је десно OK доле ОК лево ОК горе ОК десно доле десно ОК.

Оптимални редослед притискања тастера за дати пример

Морате бити улоговани како бисте послали задатак на евалуацију.